package org.ruanjj.randomizedset;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

class RandomizedSet {
    HashMap<Integer,Integer> hashMap;
    List<Integer> nums;

    public RandomizedSet() {
        hashMap = new HashMap<>();
        nums = new ArrayList<>();
    }

    public boolean insert(int val) {
        if(hashMap.containsKey(val)){
            return false;
        }else{
            nums.add(val);
            hashMap.put(val,nums.size()-1);
            return true;
        }
    }

    public boolean remove(int val) {
        if(hashMap.containsKey(val)){
            int index = hashMap.get(val);
            int last = nums.get(nums.size()-1);
            hashMap.put(last,index);
            nums.set(index,last);
            nums.remove(nums.size()-1);
            hashMap.remove(val);
            return true;
        }else{
            return false;
        }
    }

    public int getRandom() {
        Random rand = new Random();
        int randnum = rand.nextInt(nums.size());
        return nums.get(randnum);
    }
}
